home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 2010 April / PCWorld0410.iso / pluginy Firefox / 52811 / 52811.xpi / chrome / content / AES / lecuyer.js < prev    next >
Encoding:
JavaScript  |  2003-11-27  |  2.3 KB  |  96 lines
  1. /*
  2.  
  3.     L'Ecuyer's two-sequence generator with a Bays-Durham shuffle
  4.     on the back-end.  Schrage's algorithm is used to perform
  5.     64-bit modular arithmetic within the 32-bit constraints of
  6.     JavaScript.
  7.  
  8.     Bays, C. and S. D. Durham.  ACM Trans. Math. Software: 2 (1976)
  9.         59-64.
  10.  
  11.     L'Ecuyer, P.  Communications of the ACM: 31 (1968) 742-774.
  12.  
  13.     Schrage, L.  ACM Trans. Math. Software: 5 (1979) 132-138.
  14.  
  15. */
  16.  
  17. function uGen(old, a, q, r, m) {      // Schrage's modular multiplication algorithm
  18.     var t;
  19.  
  20.     t = Math.floor(old / q);
  21.     t = a * (old - (t * q)) - (t * r);
  22.     return Math.round((t < 0) ? (t + m) : t);
  23. }
  24.  
  25. function LEnext() {                   // Return next raw value
  26.     var i;
  27.  
  28.     this.gen1 = uGen(this.gen1, 40014, 53668, 12211, 2147483563);
  29.     this.gen2 = uGen(this.gen2, 40692, 52774, 3791, 2147483399);
  30.  
  31.     /* Extract shuffle table index from most significant part
  32.        of the previous result. */
  33.  
  34.     i = Math.floor(this.state / 67108862);
  35.  
  36.     // New state is sum of generators modulo one of their moduli
  37.  
  38.     this.state = Math.round((this.shuffle[i] + this.gen2) % 2147483563);
  39.  
  40.     // Replace value in shuffle table with generator 1 result
  41.  
  42.     this.shuffle[i] = this.gen1;
  43.  
  44.     return this.state;
  45. }
  46.  
  47. //  Return next random integer between 0 and n inclusive
  48.  
  49. function LEnint(n) {
  50.     var p = 1;
  51.  
  52.     //  Determine smallest p,  2^p > n
  53.  
  54.     while (n >= p) {
  55.     p <<= 1;
  56.     }
  57.     p--;
  58.  
  59.     /*  Generate values from 0 through n by first masking
  60.     values v from 0 to (2^p)-1, then discarding any results v > n.
  61.     For the rationale behind this (and why taking
  62.     values mod (n + 1) is biased toward smaller values, see
  63.     Ferguson and Schneier, "Practical Cryptography",
  64.     ISBN 0-471-22357-3, section 10.8).  */
  65.  
  66.     while (true) {
  67.         var v = this.next() & p;
  68.  
  69.     if (v <= n) {
  70.         return v;
  71.     }
  72.     }
  73. }
  74.  
  75. //  Constructor.  Called with seed value
  76.  
  77. function LEcuyer(s) {
  78.     var i;
  79.  
  80.     this.shuffle = new Array(32);
  81.     this.gen1 = this.gen2 = (s & 0x7FFFFFFF);
  82.     for (i = 0; i < 19; i++) {
  83.         this.gen1 = uGen(this.gen1, 40014, 53668, 12211, 2147483563);
  84.     }
  85.  
  86.     // Fill the shuffle table with values
  87.  
  88.     for (i = 0; i < 32; i++) {
  89.         this.gen1 = uGen(this.gen1, 40014, 53668, 12211, 2147483563);
  90.         this.shuffle[31 - i] = this.gen1;
  91.     }
  92.     this.state = this.shuffle[0];
  93.     this.next = LEnext;
  94.     this.nextInt = LEnint;
  95. }
  96.